/*******************************************************************
Copyright (c) 2018 Hacky DH

This file is distributed under MIT License.
See the LICENSE file for details.
*******************************************************************/

//==================================================================
// 《剑指Offer——名企面试官精讲典型编程题》代码
// 作者: 何海涛
//==================================================================

// 面试题42: 连续子数组的最大和
// 题目: 输入一个整型数组, 数组里有正数也有负数. 数组中一个或连续的多个整数组成一个子数组. 求所有子
// 数组的和的最大值. 要求时间复杂度为O(n).

#include <cstdio>
#include <stdexcept>

int FindGreatestSumOfSubArray(int const* data, int length) {
  if(data == nullptr || length <= 0) {
    throw std::invalid_argument("bad");
  }
  int max = 0x80000000, cur_max = 0;
  for(int i=0;i<length;++i) {
    cur_max += data[i];
    if(cur_max < data[i])
      cur_max = data[i];
    max = std::max(cur_max, max);
  }
  return max;
}

// ====================测试代码====================
void Test(char const* testName, int* pData, int nLength, int expected, bool expectedFlag) {
  if (testName != nullptr) printf("%s begins: \n", testName);

  try {
    int result = FindGreatestSumOfSubArray(pData, nLength);
    if (result == expected) {
      printf("Passed.\n");
    } else {
      printf("Failed.\n");
    }
  } catch (std::invalid_argument const& ia) {
    if (expectedFlag == true) {
      printf("Passed.\n");
    } else {
      printf("Failed.\n");
    }
  }
}

// 1, -2, 3, 10, -4, 7, 2, -5
void Test1() {
  int data[] = {1, -2, 3, 10, -4, 7, 2, -5};
  Test("Test1", data, sizeof(data) / sizeof(int), 18, false);
}

// 所有数字都是负数
// -2, -8, -1, -5, -9
void Test2() {
  int data[] = {-2, -8, -1, -5, -9};
  Test("Test2", data, sizeof(data) / sizeof(int), -1, false);
}

// 所有数字都是正数
// 2, 8, 1, 5, 9
void Test3() {
  int data[] = {2, 8, 1, 5, 9};
  Test("Test3", data, sizeof(data) / sizeof(int), 25, false);
}

// 无效输入
void Test4() {
  Test("Test4", nullptr, 0, 0, true);
}

int main(int argc, char* argv[]) {
  Test1();
  Test2();
  Test3();
  Test4();

  return 0;
}
